43E - Race - CodeForces Solution

#include<bits/stdc++.h>

using namespace std;

const int N=105;

int n,s,k[N],v[N][N],t[N][N];

int main(){

    scanf("%d%d",&n,&s);

    for(int i=1;i<=n;i++){

        scanf("%d",&k[i]);

        for(int j=1;j<=k[i];j++) scanf("%d%d",&v[i][j],&t[i][j]);

        for(int j=1;j<=k[i];j++) t[i][j]+=t[i][j-1];

        t[i][k[i]+1]=1e9;

    }

    int ans=0;

    for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++){

        int ti=0,o=2,p1=0,p2=0,s1=0,s2=0;

        while(p1!=k[i]||p2!=k[j]){

            int nt=min(t[i][p1+1],t[j][p2+1]);

            s1+=v[i][p1+1]*(nt-ti),s2+=v[j][p2+1]*(nt-ti);

            if(o!=2&&s1!=s2&&o!=(s1<s2)) ans++;

            if(s1!=s2) o=s1<s2;

            if(t[i][p1+1]<=nt) p1++;

            if(t[j][p2+1]<=nt) p2++;

            ti=nt;

        }

    }

    printf("%d\n",ans);

}